Castro Urdiales, January 2006 1

Algorithms for unimodular completion

over Noetherian rings

Ihsen Yengui

University of Sfax, Tunisia

Plan

• Symbolic computation and signal processing (By H. Park)

• An algorithm for unimodular completion over infinite fields (By A. Ellouz, H. Lombardi, I. Yengui)

• An algorithm for unimodular completion over Noetherian rings (By A. Mnif, I. Yengui)

Symbolic computation and signal processing (BY H. Park, JSC 2004)

Many signal processing problems can be modeled in the form of polynomial equations which can then be solved by the methods of computational algebra notably Gröbner bases. Definitions:

• A one-dimensional discrete time signal is a sequence of complex numbers (a_{n})_{n∈IZ} where there exists N ∈ IZ such that a_{n} = 0 for n < N. The set S of such signals equipped with superposition and convolution is a commutative ring.

• A MIMO system A : S^{p} → S^{q} can be described by the following picture:

(a_{n}^{1})_{n} ⟶ ; ⋮ ; (a_{n}^{p})_{n} ⟶  A ⟶ (b_{n}^{1})_{n} ; ⋮ ; ⟶ (b_{n}^{q})_{n}

Such a p-input q-output linear system is an operator from the module S^{p} to the module S^{p} defined by convolutions with various fixed signals.

• Perfect reconstruction:

(a_{n}^{1})_{n} ⟶ ; ⋮ ; (a_{n}^{p})_{n} ⟶  A (b_{n}^{1})_{n} ; ⟶ ; ⋮ ; ⟶ ; (b_{n}^{q})_{n}  S ⟶ (a_{n}^{1})_{n} ; ⋮ ; ⟶ (a_{n}^{p})_{n}

Suppose that when an incoming signal goes into A and the subsequent output is fed into S, the resulting output of S is identical to the original input signal of A. In this case we say that A has the perfect reconstruction property, [A, S] := PR system, A:= analysis part, S:= synthesis part.

• Algebraic formulation:

(a_{n}) → ∑ a_{n} z^{−n}

S ≅ IC[[z^{−1}]][\frac{1}{z^{−1}} ]

A p-input q-output m-dimensional linear FIR (finite sequences) system is a multiplication by a matrix A ∈ M_{qp}(IC[Z_{1}^{±}, …, Z_{m}^{±}]) (the Z-transformation representation). A has the perfect reconstruction property ⇔ A has a left inverse, that is a matrix S ∈ M_{pq}(IC[Z_{1}^{±}, …, Z_{m}^{±}]) such that

S A = I_{p}.

One important goal is to give a minimal parametrization of all left inverses of A, that is of all synthesis filter for A.

Definition: • A vector V = ^{t}(v_{1}, …, v_{n}) ∈ R^{n} is called unimodular if ⟨v_{1}, …, v_{n}⟩ = R.

• A matrix A ∈ M_{pq}(R), is called unimodular if its maximal minors generate R.

Theorem: A q × p Laurent polynomial matrix, q ≥ p, has a left inverse if and only if it is unimodular.

Park’s conversion algorithm: Via a change of variables, the above problem is transformed into a problem for multivariate polynomials over the complex numbers. This is the unimodular completion problem which is equivalent to Serre’s conjecture.

Serre’s conjecture

In 1955, J.-P. Serre remarked that it was not known whether there exist finitely generated projective modules over R = K[X_{1}, …, X_{n}], K a field, which are not free. This remark turned into the “Serre conjecture”, stating that indeed there were no such modules. Proven independently by D. Quillen and A. A. Suslin (1976), it became subsequently known as the Quillen-Suslin theorem.

It has been known since 1958 that projective modules over R are stably free, i.e, every finitely generated projective R-module is isomorphic to the kernel of an R-epimorphism T : R^{n} → R^{ℓ}. In that situation the matrix T is unimodular. By induction on ℓ, in order to obtain an algorithm for the Quillen-Suslin theorem, one has to find an algorithm for the following statement about completion of unimodular vectors.

Theorem (Unimodular completion)

Let V = ^{t}(v_{1}, …, v_{n}) ∈ K[X_{1}, …, X_{n}]^{n}, K a field and n ≥ 3, be a unimodular vector. Then there exists an invertible n × n matrix M over K[X_{1}, …, X_{n}] such that MV = ^{t}(1, 0, …, 0).

How the unimodular completion of unimodular vectors gives a minimal and complete parametrization of all synthesis filters ?

Input: A ∈ M_{pq}(IC[z_{1}, …, z_{n}]), p ≥ q, A unimodular

S_{1}A = ( \begin{matrix}1 & h_{12} & ⋯ & h_{1q} \\ 0 \\ ⋮ & & C \\ 0 \end{matrix} )

Repeat for C.

⇓
⋮

S_{q} ⋯ S_{1}A = ( \begin{matrix}1 & h_{12} & ⋯ & h_{1q} \\ 0 & 1 & ⋯ & h_{2q} \\ ⋮ & & ... & ⋮ \\ 0 & 0 & … & 1 \\ 0 & 0 & … & 0 \\ ⋮ & ⋮ & … & ⋮ \\ 0 & 0 & … & 0 \end{matrix} ) ∈ M_{p×q}

Elementary operations

⇓

ES_{q} ⋯ S_{1}A = ( \begin{matrix}1 & 0 & ⋯ & 0 \\ 0 & 1 & ⋯ & 0 \\ ⋮ & & ... & ⋮ \\ 0 & 0 & … & 1 \\ 0 & 0 & … & 0 \\ ⋮ & ⋮ & … & ⋮ \\ 0 & 0 & … & 0 \end{matrix} ) ∈ M_{p×q}

Ŝ := ES_{q} ⋯ S_{1} = ( L_{1} ; ⋮ ; L_{q} ; L_{q+1} ; ⋮ ; L_{p} )

S_{part} := ( L_{1} ; ⋮ ; L_{q} )

S_{part}A = I_{q} The synthesis matrices are exactly those of the form

S = (I_{q}, u_{1}, …, u_{p−q})Ŝ

= ( \begin{matrix}1 & 0 & ⋯ & 0 & u_{11} & … & u_{1(p−q)} \\ 0 & 1 & ⋯ & 0 & u_{21} & … & u_{2(p−q)} \\ ⋮ & ... & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & … & 1 & u_{q1} & … & u_{q(p−q)} \end{matrix} ) Ŝ

the u_{ij} are arbitrary polynomials.

Suslin’s lemma

A well-known lemma of Suslin says that for a commutative ring R if ⟨v_{1}(X), …, v_{n}(X)⟩ ∈ (R[X])^{n} is unimodular where v_{1} is monic and n ≥ 3, then there exist γ_{1}, …, γ_{ℓ} ∈ E_{n−1}(R[X]) such that ⟨Res(v_{1}, e_{1}.γ_{1} ^{t}(v_{2}, …, v_{n})), …, Res(v_{1}, e_{1}.γ_{ℓ} ^{t}(v_{2}, …, v_{n}))⟩ = R. This lemma played a central role in the resolution of Serre’s conjecture. In case R contains a set E of cardinal greater than deg v_{1} + 1 such that y − y′ is invertible for each y ≠ y′ in E, we prove that the γ_{i} can simply correspond to the elementary operations: if n = 3, L_{1} → L_{1} + y_{i}L_{2}, 1 ≤ i ≤ ℓ = deg v_{1} + 1, if n ≥ 4, L_{1} → L_{1} + y_{i} ∑_{j=2}^{n−1} u_{j+1}L_{j}, 1 ≤ i ≤ ℓ = deg v_{1} + 1, where u_{1}v_{1} + … + u_{n}v_{n} = 1.

Example: v_{1} = x^{2} − xy + 4, v_{2} = x^{2}y + 5xy + 3x − 1, v_{3} = xy^{2} + 5xy − 4y + 3x − 2 ∈ IQ[x, y]. Then setting

r_{1} := Res_{x}(v_{1}, v_{2}), r_{2} := Res_{x}(v_{1}, v_{2} + v_{3}), r_{3} := Res_{x}(v_{1}, v_{2} + 2v_{3}),

⟨r_{1}, r_{2}, r_{3}⟩ = IQ[y].

These efficient elementary operations enable us to give a new and simple algorithm for reducing unimodular rows with entries in K[X_{1}, …, X_{k}] to ^{t}(1, 0, …, 0) using elementary operations in case K is an infinite field.

An algorithm for unimodular completion (General Case)

Input: Two columns V = V(X) = ^{t}(v_{1}(X), …, v_{n}(X)), U = U(X) = ^{t}(u_{1}(X), …, u_{n}(X)) ∈ R[X]^{n} such that v_{1} is monic and V^{t}U = 1. We assume that the ring R contains elements y_{1}, …, y_{deg v_{1}+1} such that y_{i} − y_{j} is invertible for i ≠ j.

Output: A matrix B in SL_{n}(R[X]) such that B V = V(0).

Step 1: For 1 ≤ i ≤ ℓ = deg_{X} v_{1} + 1, set w_{i} := v_{2} + y_{i}(u_{3}v_{3} + ⋯ + u_{n}v_{n}), compute r_{i} := Res_{X}(v_{1}, w_{i}) and find α_{1}, …, α_{ℓ} ∈ R such that α_{1}r_{1} + ⋯ + α_{ℓ}r_{ℓ} = 1. Note that in case n = 3, one can simply take w_{i} = v_{2} + y_{i}v_{3} instead of v_{2} + y_{i}u_{3}v_{3}. For 1 ≤ i ≤ ℓ, compute f_{i}, g_{i} ∈ R[X] such that f_{i}v_{1} + g_{i}w_{i} = r_{i}.

Step 2: Set

b_{ℓ} := 0, b_{ℓ−1} := α_{ℓ} r_{ℓ}X, b_{ℓ−2} := b_{ℓ−1} + α_{ℓ−1}r_{ℓ−1}X, ⋮ b_{0} := b_{1} + α_{1}r_{1}X = X.

Step 3: For 1 ≤ i ≤ ℓ, find B_{i} ∈ SL_{n}(R[X]) such that B_{i}V(b_{i−1}) = V(b_{i}).

Step 4: B := B_{ℓ} ⋯ B_{1}.

To have an algorithm for unimodular completion over K[X_{1}, …, X_{k}], K an infinite field, it suffices to perform for 1 ≤ j ≤ k the general algorithm above with A = K[X_{1}, …, X_{j−1}] and X = X_{j}. Note that via a linear change of variables we can always suppose that the first coordinate of the given unimodular vector is monic.

An example

Let A = V = ( \begin{matrix}v_{1} \\ v_{2} \\ v_{3} \end{matrix} ) = ( \begin{matrix}x − 4y + 2 \\ xy + x \\ x + 4y^{2} − 2y + 1 \end{matrix} ) ∈ Um_{3}(IQ[x, y]).

A is the analysis part of a 1-input 3-output 2-dimensional linear FIR system.

B = ( \begin{matrix}−xy + 1 & x & −x \\ −xy^{2} − xy & xy + x + 1 & −xy − x \\ −xy & x & −x + 1 \end{matrix} ) ,

G = E_{2,1}(−1) E_{1,2}(1) E_{3,2}(−4y^{2}+2y−1) E_{1,2}(4y−2) E_{2,3}(1) E_{2,1}(y) B.

G ( \begin{matrix}x − 4y + 2 \\ xy + x \\ x + 4y^{2} − 2y + 1 \end{matrix} ) = ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} )

Conclusion: A minimal and complete parametrization of 3-input 1-output synthesis filters for A is of the form

S = (1, u_{1}, u_{2}) G

= (1 + 4y^{2} − y, 4y − 1, 4y − 1) + u_{1}(−1 − 4y^{2} + 2y, −4y + 2, −4y + 2)

+u_{2}(−y − 4y^{3} + 2y^{2}, −1 − 4y^{2} + 2y, −4y^{2} + 2y).

Castro Urdiales, January 2006 23

A comparison between some algorithms for unimodular completion

C.S  F.G  L.Y  E.Y
N.F  O(k^{2} d^{2} n^{2})  2k d n^{2}  4k d(2n + 1)  k d (4n − 7)
D.B  d^{O(k)}  d^{O(k)}  O(n^{2}d^{k})  k d^{5}(d^{k} + d + 3)^{3}
C.B  n^{4}d^{O(k^{2})}  n^{4}d^{O(k^{2})}  (nd)^{O(k^{2})}  n^{3}d^{O(k^{2})}

L.S, P.W: non provided

An algorithm for unimodular completion over Noetherian rings

Our goal now is to give an algorithm for the well-known generalization of the theorem about unimodular completion above asserting that if R is a Noetherian ring of Krull dimension d < ∞, then for n ≥ max(3, d + 2), SL_{n}(R[X_{1}, …, X_{k}]) acts transitively on Um_{n}(R[X_{1}, …, X_{k}]). For technical reasons we demand that the Noetherian ring R has a theory of Gröbner bases and contains an infinite set E = {y_{1}, y_{2}, ...} such that y_{i} − y_{j} is invertible when i ≠ j. The most important guiding examples are affine rings K[X_{1}, …, X_{m}]/I, and localizations of polynomial rings S^{−1}K[X_{1}, …, X_{m}], K an infinite field.

Lemma

Suppose that uv + w = 1 in a Noetherian ring R containing an infinite set E = {y_{1}, y_{2}, ...} such that y_{i} − y_{j} is invertible when i ≠ j. Then there exists i such that v + y_{i}w is not a zero divisor.

Theorem Suppose that u_{1}v_{1} + u_{2}v_{2} + ⋯ + u_{n}v_{n} = 1 in a Noetherian ring R containing an infinite set E = {y_{1}, y_{2}, ...} such that y_{i} − y_{j} is invertible when i ≠ j. Then there exist y_{1}, …, y_{n−1} ∈ E such that the sequence (v_{1} + y_{1}ξ_{0}(u_{2}v_{2} + ⋯ + u_{n}v_{n}), v_{2} + y_{2}ξ_{1}(u_{3}v_{3} + ⋯ + u_{n}v_{n}), …, v_{n−1} + y_{n−1}ξ_{n−2}u_{n}v_{n}) is regular, where ξ_{0} = 1 and ξ_{k+1} = ξ_{k}(1 − y_{k+1}u_{k+1}ξ_{k}).

Corollary ( An algorithm for the basic ring)

Let R be a Noetherian ring with dim R = d < ∞ and suppose that R contains an infinite set E = {y_{1}, y_{2}, ...} such that y_{i} − y_{j} is invertible when i ≠ j. If u_{1}v_{1} + u_{2}v_{2} + ⋯ + u_{n}v_{n} = 1 in R with n ≥ d + 2, then denoting w_{k} = u_{k}v_{k} + ⋯ + u_{n}v_{n}, there exist y_{1}, …, y_{d+1} ∈ E such that

1 ∈ ⟨v_{1} + y_{1}ξ_{0}w_{2}, v_{2} + y_{2}ξ_{1}w_{3}, …, v_{d+1} + y_{d+1}ξ_{d}w_{d+2}⟩,

where ξ_{0} = 1 and ξ_{k+1} = ξ_{k}(1 − y_{k+1}u_{k+1}ξ_{k}). In particular, there exists M ∈ E_{n}(R) such that

M ^{t}(v_{1}, v_{2}, …, v_{n}) = ^{t}(1, 0, …, 0).

If R is a ring, the ring R⟨X⟩ denotes the localization of the polynomial ring R[X] at the multiplicative subset of monic polynomials. By induction, we define

R⟨X_{1}, …, X_{k}⟩ := R⟨X_{1}, …, X_{k−1}⟩⟨X_{k}⟩.

It is in fact the localization of the polynomial ring R[X_{1}, …, X_{k}] at the multiplicative subset

U_{k} = {f ∈ R[X_{1}, …, X_{k}] such that LC(f) = 1},

where LC(f) denotes the leading coefficient of f related to the lexicographic monomial order with X_{k} > X_{k−1} > ⋯ > X_{1}.

It is well-known that if R is Noetherian then

dim R⟨X_{1}, …, X_{k}⟩ = dim R

but up to now we did not manage to obtain a constructive proof of this result using one of the equivalent constructive definitions of the Krull dimension given in numerous papers co-written by Lombardi on this subject. So, the following result is only algorithmic and not fully constructive. All the necessary computations can be done with Gröbner bases techniques.

Monic Coordinate algorithm

Let R be a computable Noetherian ring with dim R = d < ∞ and suppose that R contains an infinite set E = {y_{1}, y_{2}, ...} such that y_{i} − y_{j} is invertible when i ≠ j. If u_{1}v_{1} + u_{2}v_{2} + ⋯ + u_{n}v_{n} = 1 in R[X_{1}, …, X_{k}] with n ≥ d + 2, then denoting w_{k} = u_{k}v_{k} + ⋯ + u_{n}v_{n}, there exist y_{1}, …, y_{d+1} ∈ E such that

⟨v_{1} + y_{1}ξ_{0}w_{2}, v_{2} + y_{2}ξ_{1}w_{3}, …, v_{d+1} + y_{d+1}ξ_{d}w_{d+2}⟩ ∩ U_{k} ≠ ∅,

where ξ_{0} = 1 and ξ_{k+1} = ξ_{k}(1 − y_{k+1}u_{k+1}ξ_{k}). In particular, via a change of variables and by elementary operations we can transform ^{t}(v_{1}, v_{2}, …, v_{n}) into a unimodular row whose first coordinate is monic at X_{k}.

\underline{X} := (X_{1}, …, X_{k})

An algorithm for unimodular completion over Noetherian rings

Input: Two columns V = V(\underline{X}) = ^{t}(v_{1}(\underline{X}), …, v_{n}(\underline{X})), U = U(\underline{X}) = ^{t}(u_{1}(\underline{X}), …, u_{n}(\underline{X})) ∈ R[\underline{X}]^{n} such that V^{t}U = 1. We assume that R is a computable Noetherian ring, R contains infinitely many y_{i} such that y_{i} − y_{j} is invertible for i ≠ j, dim R = d < ∞ and n ≥ max(3, d + 2).

Output: A matrix M in SL_{n}(R[\underline{X}]) such that MV = ^{t}(1, 0, …, 0).

Step 1: Make a change of variables and elementary operations on V so that v_{1} becomes monic at X_{k} (follow the algorithm Monic Coordinate).

Step 2: Perform the general algorithm for unimodular completion to eliminate X_{k}.

Step 3: Repeat for V(X_{1}, …, X_{k−1}, 0).

Step 4: (basic step) Follow the “algorithm for the basic ring” to transform V(0, …, 0) into ^{t}(1, 0, …, 0) using elementary operations.

An example

I := ⟨a^{2} − a, b^{2} − b, ab⟩, R := IQ[a, b]/I.

Recall that for any ideal J of K[x] := K[x_{1}, …, x_{n}], K field, dim K[x]/J = K[x]/L(J), and for any monomial ideal J′ = ⟨m_{1}, …, m_{s}⟩, we have the recursive formula:

d(J′, K[x]) := dim K[x]/J′ = max{d(J′\_{x_{i}=0}, K[x \ x_{i}]), x_{i} / m_{1}},

with the assumption dim K = 0, dim K[x_{1}, …, x_{k}] = k.

Castro Urdiales, January 2006 33

So dim R = dim IQ[a, b]/⟨a^{2} − a, b^{2} − b, ab⟩ = dim IQ[a, b]/⟨a^{2}, b^{2}, ab⟩

= dim IQ[b]/⟨b^{2}⟩ = dim IQ = 0.

Let ; V = ( \begin{matrix}(b − 1)x + 1 − b \\ bx − a \\ −ax − 1 \end{matrix} ) ∈ Um_{3}(R[x]). ; M = ( \begin{matrix}1 + ax & −ax + 2x − 2bx & −b + bx − x \\ a − 2bx + ax & 1 + ax & −ax + bx \\ 1 + 2ax & −2bx + 2x & −x + bx + 1 − ax − b \end{matrix} ) , ; M V = ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ) .